package leetcode.editor.cn;

import java.util.Arrays;

/**
 * 最长公共子序列
 * @author qulq
 * @date 2024-07-28 10:54:12
 */
public class T1143_LongestCommonSubsequence{
	 public static void main(String[] args) {
	 	 // 测试代码
	 	 Solution solution = new T1143_LongestCommonSubsequence().new Solution();
	 }
	/**
	 * f[i][j] :A的前i个、B的前j个的最长....
	 * f[i][j] = max(f[i-1][j], f[i][j-1], f[i-1][j-1] | Ai-1 = Bj-1)
	 */
// 力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
		char[] c1 = text1.toCharArray();
		char[] c2 = text2.toCharArray();
		int[][] dp = new int[c1.length + 1][c2.length + 1];
		int ans = 0;
		for (int i = 0; i <= c1.length; i++) {
			for (int j = 0; j <= c2.length; j++) {
				if (i == 0 || j == 0) {
					dp[i][j] = 0;
					continue;
				}
				dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
				if (c1[i - 1] == c2[j - 1]) {
					dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
				}
				ans = Math.max(ans, dp[i][j]);
			}
		}
		return ans;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}